package sort.simple;

import org.junit.Test;

import java.util.Arrays;

public class ShellSort {
    @Test
    public void test() {
//        Integer[] nums = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        Integer[] nums = {5, 2, 7, 4, 1, 3, 8, 9};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void sort(Comparable[] a) {
        int len = a.length;
        int h = 1;
        while (h < len / 2) {   //确定增量值（步长）
            h = h * 2 + 1;
        }

        //当增量值小于1时排序完成
        while (h >= 1) {    //当h>=1时就进行一次分组，并完成各个组的插入排序
            for (int i = h; i < len; i++) {       // 一开始i的位置是从h开始的，因为 i-h是分组的第一个元素，默认是有序的
//                因为i每次都加1，所以内循环的目的就是将i所在位置及其之前同一个分组的元素进行插入排序（后面的没扫到就没排，这其实就是插入排序的思想呀）
                for (int j = i; j >= h; j -= h) { // j会对同一个分组内的元素进行比较，完成插入排序
                    if (greater(a[j-h], a[j])) {  // 如果j位置的元素比前面的有序数组小,需要将其交换，插入有序数组中
                        swap(a, j, j - h);
                    }else { //不需要进行交换，说明分组内是有序的
                        break;
                    }
                }
            }
            h /= 2;
        }
    }


    public void swap(Comparable[] c, int i, int j) {
        Comparable temp = c[i];
        c[i] = c[j];
        c[j] = temp;
    }

    public boolean greater(Comparable c1, Comparable c2) {
        return c1.compareTo(c2) > 0;
    }
}
